package library;

public class myMath {
    /*
     * 作用：求两个数的最大公约数
     * 描述：stein求最大公约数
     * 注意：方法名带前缀_表示保证传入的数字为非负数
     * 步骤：
     *      x,y均为奇数
     *      1.gcd(2x,y)=gcd(x,y)
     *      2.gcd(2x,2y)=2*gcd(x,y)
     *      3.gcd(x,y)=gcd(abs(x-y),min(x,y))
     */
    public static int _gcd(int a, int b) {
        int k = 1;
        while ((a & 1) == 0 && (b & 1) == 0) {
            a >>= 1;
            b >>= 1;
            k <<= 1;
        }
        while ((a & 1) == 0) {
            a >>= 1;
        }
        while ((b & 1) == 0) {
            b >>= 1;
        }
        while (a != b) {
            if (a < b) a ^= b ^ (b = a);
            a -= b;
        }
        return k * a;
    }

    public static long _gcd(long a, long b) {
        long k = 1;
        while ((a & 1) == 0 && (b & 1) == 0) {
            a >>= 1;
            b >>= 1;
            k <<= 1;
        }
        while ((a & 1) == 0) {
            a >>= 1;
        }
        while ((b & 1) == 0) {
            b >>= 1;
        }
        while (a != b) {
            if (a < b) a ^= b ^ (b = a);
            a -= b;
        }
        return k * a;
    }

    public static int gcd(int a, int b) {
        return _gcd(Math.abs(a), Math.abs(b));
    }

    public static long gcd(long a, long b) {
        return _gcd(Math.abs(a), Math.abs(b));
    }

    /*
     * 作用：求多个数的最大公约数
     * 注意：方法名带前缀_表示保证传入的数字为非负数
     */
    public static int gcd(int a, int b, int... args) {
        int ans = _gcd(Math.abs(a), Math.abs(b));
        for (int element : args) {
            ans = _gcd(ans, Math.abs(element));
        }
        return ans;
    }

    public static long gcd(long a, long b, long... args) {
        long ans = _gcd(Math.abs(a), Math.abs(b));
        for (long element : args) {
            ans = _gcd(ans, Math.abs(element));
        }
        return ans;
    }

    /*
     * 作用：求两个数的最小公倍数
     * 注意：方法名带前缀_表示保证传入的数字为非负数
     */
    public static int _lcm(int a, int b) {
        return a / _gcd(a, b) * b;
    }

    public static int lcm(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        return a / _gcd(a, b) * b;
    }

    public static long _lcm(long a, long b) {
        return a / _gcd(a, b) * b;
    }

    public static long lcm(long a, long b) {
        a = Math.abs(a);
        b = Math.abs(b);
        return a / _gcd(a, b) * b;
    }

    /*
     * 作用：求多个数的最小公倍数
     * 注意：方法名带前缀_表示保证传入的数字为非负数
     */
    public static int _lcm(int a, int b, int... args) {
        int ans = _lcm(a, b);
        for (int element : args) {
            ans = _lcm(ans, element);
        }
        return ans;
    }

    public static long _lcm(long a, long b, long... args) {
        long ans = _lcm(a, b);
        for (long element : args) {
            ans = _lcm(ans, element);
        }
        return ans;
    }

    public static int lcm(int a, int b, int... args) {
        int ans = lcm(a, b);
        for (int element : args) {
            ans = _lcm(ans, Math.abs(element));
        }
        return ans;
    }

    public static long lcm(long a, long b, long... args) {
        long ans = lcm(a, b);
        for (long element : args) {
            ans = _lcm(ans, Math.abs(element));
        }
        return ans;
    }

    /*
     * 作用：求ax+by=gcd(a,b)的(x,y)的可行解，并返回gcd(a,b)
     * 注意：该gcd可能为负数
     * 描述：由于Java无C++式的引用(&)，所以以数组形式表示(x,y) → (arr[0],arr[1])
     */
    public static int exgcd(int a, int b, int[] arr) {
        if (b == 0) {
            arr[0] = 1;
            arr[1] = 0;
            return a;
        }
        int gcd = exgcd(b, a % b, arr);
        int t = arr[0];
        arr[0] = arr[1];
        arr[1] = t - a / b * arr[1];
        return gcd;
    }

    public static long exgcd(long a, long b, long[] arr) {
        if (b == 0) {
            arr[0] = 1;
            arr[1] = 0;
            return a;
        }
        long gcd = exgcd(b, a % b, arr);
        long t = arr[0];
        arr[0] = arr[1];
        arr[1] = t - a / b * arr[1];
        return gcd;
    }

    /*
     * 作用：求a在模m意义下的乘法逆元
     * 描述：扩展欧几里得求乘法逆元
     *      若该数不存在在模m意义下的乘法逆元，则抛出异常
     * 注意：方法名带前缀_的为结果可能为负数
     */
    public static int _inv(int a, int m) {
        if (a == 0) {
            throw new RuntimeException("0不存在在乘法逆元");
        }
        int u = 0, v = 1, t;
        while (a != 0) {
            t = m / a;
            m -= t * a;
            a ^= m ^ (m = a);
            u -= t * v;
            u ^= v ^ (v = u);
        }
        if (m != 1) {
            throw new RuntimeException("所传入的两个参数不互质");
        }
        return u;
    }

    public static long _inv(long a, long m) {
        if (a == 0) {
            throw new RuntimeException("0不存在在乘法逆元");
        }
        long u = 0, v = 1, t;
        while (a != 0) {
            t = m / a;
            m -= t * a;
            a ^= m ^ (m = a);
            u -= t * v;
            u ^= v ^ (v = u);
        }
        if (m != 1) {
            throw new RuntimeException("所传入的两个参数不互质");
        }
        return u;
    }

    public static int inv(final int a, final int m) {
        int ans = _inv(a, m);
        while (ans < 0) ans += m;
        return ans;
    }

    public static long inv(final long a, final long m) {
        long ans = _inv(a, m);
        while (ans < 0) ans += m;
        return ans;
    }

    /*
     * 作用：判断n是否为质数
     * 描述：余6法判断质数
     *      当x%6=±1时，x可能是质数，否则一定不是质数
     */
    //余6法
    //当x%6=±1时，x可能是质数，否则一定不是质数
    public static boolean isPrime(int n) {
        if (n <= 3) return n > 1;
        if (n % 6 != 1 && n % 6 != 5) return false;
        for (int i = 5, sqrt = (int) Math.sqrt(n); i <= sqrt; i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }

    public static boolean isPrime(long n) {
        if (n <= 3) return n > 1;
        if (n % 6 != 1 && n % 6 != 5) return false;
        for (long i = 5, sqrt = (long) Math.sqrt(n); i <= sqrt; i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }

}
